1263E - Editor - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ff first
#define ss second
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define mp make_pair
#define ld long double
#define uset unordered_set
#define umap unordered_map
#define umset unordered_multiset
#define ummap unordered_multimap
#define pii pair<int, int>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pll pair<long long, long long>
#define bint __int128

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int inf = 1e9;
struct node {
    int mx = -inf;
    int mn = inf;

    node(): mx(-inf), mn(inf) {}

    node(int mx, int mn): mx(mx), mn(mn) {}
};

node operator+(node a, node b) {
    return {max(a.mx, b.mx), min(a.mn, b.mn)};
}

struct segtree {
    int sz;
    vector<node> tree;
    vector<int> push;

    void init(int n) {
        sz = 1;
        while (sz < n)
            sz *= 2;
        tree.resize(2 * sz, node(0, 0));
        push.resize(2 * sz);
    }

    void prop(int x, int tl, int tr) {
        if (tr - tl == 1 || push[x] == 0)
            return;
        push[2 * x + 1] += push[x];
        push[2 * x + 2] += push[x];
        tree[2 * x + 1].mx += push[x];
        tree[2 * x + 1].mn += push[x];
        tree[2 * x + 2].mx += push[x];
        tree[2 * x + 2].mn += push[x];
        push[x] = 0;
    }

    void add(int l, int r, int v, int x, int tl, int tr) {
        prop(x, tl, tr);
        if (l <= tl && tr <= r) {
            tree[x].mx += v;
            tree[x].mn += v;
            push[x] += v;
            return;
        }
        if (l >= tr || r <= tl)
            return;
        int m = (tl + tr) / 2;
        add(l, r, v, 2 * x + 1, tl, m);
        add(l, r, v, 2 * x + 2, m, tr);
        tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
    }

    void add(int l, int r, int v) {
        add(l, r, v, 0, 0, sz);
    }

    node get(int l, int r, int x, int tl, int tr) {
        prop(x, tl, tr);
        if (l <= tl && tr <= r)
            return tree[x];
        if (l >= tr || r <= tl)
            return node();
        node s1, s2;
        int m = (tl + tr) / 2;
        s1 = get(l, r, 2 * x + 1, tl, m);
        s2 = get(l, r, 2 * x + 2, m, tr);
        return s1 + s2;
    }

    node get(int l, int r) {
        return get(l, r, 0, 0, sz);
    }
};

inline void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> a(n);
    int cur = 0;
    segtree st;
    st.init(n);
    for (char com : s) {
        if (com == 'L') {
            cur--;
            if (cur < 0)
                cur = 0;
        } else if (com == 'R') {
            cur++;
        } else {
            int nv;
            if (com == '(')
                nv = 1;
            else if (com == ')')
                nv = -1;
            else
                nv = 0;
            st.add(cur, n, nv - a[cur]);
            a[cur] = nv;
        }
        node minmax = st.get(0, n);
        node e = st.get(n - 1, n);

        if (e.mx) {
            cout << -1 << ' ';
            continue;
        }
        if (minmax.mn < 0)
            cout << -1 << ' ';
        else
            cout << minmax.mx << ' ';
    }
    cout << '\n';
}

signed main() {
#ifndef DEBUG
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);
#endif
    int tt = 1;
#ifdef DEBUG
    std::cin >> tt;
#endif
    while (tt--) {
#ifdef DEBUG
        std::cout << "Test case#\n";
#endif
        solve();
    }
    return 0;
}